// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
// "3": "def",
// "2": "abc",
// "4": "ghi",
// "5": "jkl",
// "6": "mno",
// "7": "pqrs",
// "8": "tuv",
// "9": "wxyz",

function letterCombinations(digits: string): string[] {
  if (!digits) return []; // 边界检测
  const queue: string[] = []; // 队列
  const letterMap: { [key: string]: string } = {
    // 哈希表
    "3": "def",
    "2": "abc",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
  };
  queue.push("");
  for (let i = 0; i < digits.length; i++) {
    let currSize: number = queue.length;
    let matchStr: string = letterMap[digits[i]];
    for (let j = 0; j < currSize; j++) {
      let curr: string = queue.shift()!; // 第一个元素出队
      for (let k = 0; k < matchStr.length; k++) {
        queue.push(curr + matchStr[k]);
      }
    }
  }
  return queue;
}

// 这道题目是一道比较经典的例题，常规的解法包含循环递归和采用队列的解法
// 这里采用的是基于队列的解法，利用的是队列先进先出的特点
// 内部先声明好一个哈希表
// 我们先思考比较简单的情况，‘23’的情况下，我们实际上先取到'2'对应的哈希表值'abc'入队
// 入队后每次出队取到单个字符串'a'，然后与'3'对应的哈希表值'def'进行单个字符串的组合
// 组合后形成'ad'\'ae'\'af'再重新入队，当我们扫描到最后一个数字且完成出队入队操作时
// 队列的结果即为最后输出的结果。

function letterCombinations2(digits: string): string[] {
  if (digits === "") return []; // 安全监测
  const res: string[] = []; // 结果数组
  const letterMap: { [key: string]: string } = {
    // 记录的哈希表
    "3": "def",
    "2": "abc",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
  };
  letter_DFS(digits, "", 0);
  return res;
  // 内部深度优先递归遍历函数
  function letter_DFS(digits: string, currStr: string, index: number) {
    if (index === digits.length) {
      // 递归出口，深度达到输入字符的长度
      res.push(currStr);
      return;
    }
    let matchStr: string = letterMap[digits[index]]; // 匹配的字符串
    for (let i = 0; i < matchStr.length; i++) {
      letter_DFS(digits, currStr + matchStr[i], index + 1);
    }
  }
}

// 同理这道题存在深度优先遍历的解法
// 比较难以理解的部分是在循环里套了递归，为什么要这么设计？
// 递归在这里实际上是模拟多层for循环嵌套的情况（仔细思考这句话）
// 实质上这题的组合可以画成一个深度优先遍历的情况，根节点是空字符串
// 每层子树的分支就是当前深度对应索引的哈希表匹配字母的分支
// 思考我们对'23'的处理，实际上是通过两层循环排列组合求得的，
// 同理我们对'234'的处理，需要通过三层循环来做排列组合
// 因为我们拿到了输入数字的长度，也可以通过递归来实现多层循环的排列组合。
